package com.hanxiaozhang.no10leetcode.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈将一棵二叉树以自底向上的方式，将其每一层中的节点值输出到数组中（从左到右，从叶到根）〉
 * <p>
 * 实例:
 * 给定二叉树：[3,9,20,null,null,15,7]
 * .    3
 * .   / \
 * .  9  20
 * .    /  \
 * .   15   7
 * 返回其自下而上级别的顺序遍历为:
 * [
 * [15,7],
 * [9,20],
 * [3]
 * ]
 * <p>
 * 思路：
 * 1.使用递归，递归入参中记录当前层数。->
 * 记录当前层数的目的是保证每层添加到不同集合中。
 * 2.自下而上排序，通过使用List.add(0,xx)，即每次在头部添加。
 *
 * @author hanxinghua
 * @create 2024/4/11
 * @since 1.0.0
 */
public class No107BinaryTreeLevelOrderTraversalII {

    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(3);
        tree1.left = new TreeNode(9);
        tree1.right = new TreeNode(20);
        tree1.right.left = new TreeNode(15);
        tree1.right.right = new TreeNode(7);

        System.out.println(method1(tree1));

    }


    /**
     * 方法1
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> method1(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();

        // 处理特殊值
        if (root == null) {
            return res;
        }

        recursion(res, root, 1);
        return res;
    }


    /**
     * 递归
     *
     * @param res   结果
     * @param root  二叉树
     * @param level 当前层级
     */
    private static void recursion(List<List<Integer>> res, TreeNode root, int level) {
        if (root == null) {
            return;
        }

        // 当前层级 大于 结果集个数时，需要创建一个新集合
        if (level > res.size()) {
            // 特殊点：LinkedList 用在第0索引位置插入新的集合
            res.add(0, new ArrayList<>());
        }
        // 此时 res.size() == level  ->  res.size() - level = 0  -> 即永远在第0索引位置的集合中添加
        System.out.println(res.size() - level);
        res.get(res.size() - level).add(root.val);

        recursion(res, root.left, level + 1);
        recursion(res, root.right, level + 1);
    }
}
